1. Field of the Invention
The present invention relates to data processing apparatuses which are configured to generate randomized values.
2. Description of the Prior Art
It is known that random number generation plays a crucial role in cryptography and security. For example, public key cryptography systems demand strong key pair generation to ensure that a third-party cannot decrypt a secret message. Previously, random bit sequences have been generated in digital systems using pseudo-random number generators. However, the sequences produced by these generators are not truly random and contain exploitable patterns, such as repetition and correlation.
Accordingly, true random number generators (tRNGs) use physical phenomena as a random source to produce bits. Previous on-chip tRNG architectures have used telegraph noise (Brederlow, R., et al., “A Low-Power True Random Number Generator using Random Telegraph Noise of Single Oxide-Traps,” ISSCC, February 2006) and thermal noise as the physical source. The thermal noise is often used indirectly with a metastable inverter (Holleman, J., et al., “A 3 μW CMOS True Random Generator With Adaptive Floating-Gate Offset Cancelation,” JSSC, May 2008; Tokunaga, C., et al., “True Random Number Generator with a Metastability-Based Quality Control,” IEEE Journal of Solid-State Circuits, January 2008; Kinniment, D., et al., “Design of an On-Chip Random Number Generator using Metastability,” ESSCIRC, September 2002; Srinivasan, S., et al., “2.4 GHz 7 mW All-Digital PVT-Variation Tolerant True Random Number Generator in 45 nm CMOS,” VLSIC, June 2010), a jitter-prone oscillator (Bucci, M., et al., “A High-Speed Oscillator-Based Truly Random Number Source for Cryptographic Applications on a Smart Card IC,” IEEE Transactions on Computers, April 2003; Petrie, C., et al., “A Noise-Based IC Random Number Generator for Applications In Cryptography,” IEEE Transactions on Circuits and Systems, May 2000) or a discrete-time chaotic pipelined structure (Pareschi, F., et al., “A Fast Chaos-Based True Random Number Generator for Cryptographic Applications,” ESSCIRC, September 2006). An alternative approach has used fluctuating gate oxide current after soft breakdown (SBD) as a noise source (Yasuda, S. et al., “Physical Random Number Generator Based on MOS Structure After Soft Breakdown”, JSSC, August 2004). Aspects of oxide breakdown are discussed, for example, in Stathis, J., Journal of Applied Physics, pp. 5757-5766, Vol. 86, November 1999. Once an oxide breaks down, its resistance changes from an essentially infinite value to the order of MΩ or kΩ (see Kim, J. and Lee, K., Electron Device Letters, pp. 589-591, September 2003), a characteristic which has led to its use in one-time programmable arrays (Ito, H. and Namekawa, T., CICC, pp. 469-472, 2004; P. Candelier et al., IRPS, pp. 169-173, 2000; and Cha, H.-K. et al., JSSC, pp. 2115-2124, Vol. 41, No. 9, September 2006).
However, many of these prior architectures have relied on an invasive post-processing step to remove bias in the generated stream, a process which heavily modifies the bitstream and brings into doubt its randomness. For example, a common modifier is a von Neumann corrector to remove long runs of 0's and 1's. In addition, the architectures that do not require a post-processor have only been able to pass five of the fifteen statistical randomness tests in the NIST 800-22 benchmark “National Institute of Standards and Technology, “A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications,” Pub. 800 22 2001), the accepted standard test for true randomness. In addition, many prior art generators require precise, involved statistical calibration in order to ensure randomness. In particular, recalibration is often required when environmental conditions (e.g. ambient temperature) change.
One particular application where randomized (unique) value generation is required is in the provision of unique chip ID values, for example as are used to enforce user licenses as well as in communication and security protocols. In these applications, it is desirable to generate IDs on-chip at the application point so that the IDs are guaranteed to be previously unknown. This avoids the need for off-chip, pre-generated IDs that are programmed using fuses, a process that exposes IDs to human intervention and storage on computers that may be compromised.
It is known that a key requirement for chip ID generation is that the generated ID is unique to only that chip, and that once generated the ID is time and environmentally invariant. Typically, the chances that two chip IDs have all (or at least many) bits the same is minimized by using a large bit width (e.g. 128 bits/ID) and ensuring a high degree of randomness during generation. Previous methods rely on inherent threshold voltage mismatch between devices, which is detected by measuring either device current (K. Lofstrom, et al., ISSCC, pp. 372-373, 2000) or inherent SRAM bit cell skew towards a 0 or 1 state (Y. Su, et al., ISSCC, pp. 406-407, 2007). However threshold voltage mismatch can be very small between any particular transistor pair, making it difficult to repeatedly generate an identical ID for a given chip. As a result, previous approaches exhibit as a result a small number of bit flips between successive ID readings (i.e. the IDs have a non-zero self Hamming distance), complicating the use and the reliability of the chip IDs generated.
It would be desirable to provide an improved technique for generating such randomized values, in the light of the above-mentioned particular drawbacks of the prior art.